package f_graph_basics.e_shortest_path;

import f_graph_basics.a_graph_representation.Graph;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.Queue;

/**
 * 广度优先（层序）遍历 - 获得无权图的最短路径
 */
public class GraphShortestPath {
    private final int FALSE = 0;
    private final int TRUE = 1;
    private Graph g ;
    private int s; // vertex to start with
    private int[] visited; // visited[v] 从s开始进行路径遍历过程中 如果访问过某节点v 将值设置成1 默认为0
    private int[] from; // from[v] 从s开始并且经过v的路径中v之前访问的节点， 默认为 -1
    private int[] ord; // ord[v]从s到v的路径遇到的节点数 默认为 -1

    public boolean hasPath(int w) {
        assert w >= 0 && w < g.v();
        return visited[w] == TRUE;
    }

    public GraphShortestPath(Graph g, int s) {
        this.g = g;
        this.s = s;
        int len = g.v();
        // 算法初始化
        assert s >= 0 && s< len;
        visited = new int[len];
        from = new int[len];
        ord = new int[len];
        for (int i = 0; i < len; i++) {
            visited[i] = FALSE;
            from[i] = -1;
            ord[i] = -1;
        }
        Queue<Integer> q = new ArrayDeque<>();

        //无向图最短路径算法
        q.add(s);
        visited[s] = TRUE;
        ord[s] = 0;

        while (!q.isEmpty()) {
            int v = q.poll();
            ArrayList<Integer> edges = this.g.getEdgesByVertex(v);
            for (Integer e  : edges ) {
                if (visited[e] != TRUE) {
                    q.add(e);
                    visited[e] = TRUE;
                    from[e] = v;
                    ord[e] = ord[v] + 1;
                }
            }
        }
    }

    /**
     * 寻路
     * 打印s-w的所有路径
     *
     * @param w
     */
    public void printPath(int w) {
        ArrayList<Integer> vec = new ArrayList<>();
        Deque<Integer> stack = new ArrayDeque<>();
        int p = w;
        while (p != -1) {
            stack.push(p);
            p = from[p];
        }
        vec.clear();
        while (!stack.isEmpty()) {
            vec.add(stack.peek());
            stack.pop();
        }
        for (int i = 0; i < vec.size(); i++) {
            System.out.print(vec.get(i));
            if (i == vec.size() - 1) {
                System.out.println();
            } else {
                System.out.print(" -> ");
            }
        }
    }

    /**
     * 返回s到w的路径长度 - 中间经历节点的个数
     * @param w
     * @return
     */
    public int len(int w) {
        assert w >= 0 && w < g.v();
        return ord[w];
    }
}
